package org.example;

import org.junit.jupiter.api.Test;

import java.util.stream.IntStream;

public class Dp {

    int[] wgt = {10, 20, 30, 40, 50};
    int[] val = {50, 120, 150, 210, 240};
    int cap = 50;

    @Test
    void bagV1() {
        int n = wgt.length;
        int[][] dp = new int[n + 1][cap + 1];

        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                int w = wgt[i - 1];
                if (w > c) {
                    dp[i][c] = dp[i - 1][c];
                    continue;
                }

                dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - w] + val[i - 1]);
            }
        }

        System.out.println(122);
    }

    /**
     * 空间优化 + 可重复
     */
    @Test
    void bagV2() {
        int n = wgt.length;
        int[] dp = new int[cap + 1];

        for (int i = 1; i <= n; i++) {
            System.out.println(111);
            for (int c = 1; c <= cap; c++) {
                int w = wgt[i - 1];
                if (w > c) {
                    continue;
                }

                dp[c] = Math.max(dp[c], dp[c - w] + val[i - 1]);
            }
        }

        System.out.println(dp[cap]);
        System.out.println(122);
    }

    /**
     * 空间优化 + 不可重复 + 后序处理
     */
    @Test
    void bagV3() {

        int n = wgt.length;
        int[] dp = new int[cap + 1];

        for (int i = 1; i <= n; i++) {
            System.out.println(111);
            for (int c = cap; c >= 1; c--) {
                int w = wgt[i - 1];
                if (w > c) {
                    continue;
                }

                dp[c] = Math.max(dp[c], dp[c - w] + val[i - 1]);
            }
        }

        System.out.println(dp[cap]);
        System.out.println(122);
    }

    @Test
    void coinChange() {
        int[] coins = {1, 2, 5};
        int amt = 9;
        int n = coins.length;
        int[][] dp = new int[n + 1][amt + 1];

        IntStream.rangeClosed(1, amt).forEach(j -> dp[0][j] = amt + 1);

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amt; j++) {
                int coin = coins[i - 1];
                if (coin > j) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }

                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coin] + 1);
            }
        }

        System.out.println(dp[n][amt]);
    }

    @Test
    void coinChangeV2() {
        int[] coins = {1, 2, 5};
        int amt = 5;
        int n = coins.length;
        int[][] dp = new int[n + 1][amt + 1];

        IntStream.rangeClosed(0, n).forEach(i -> dp[i][0] = 1);

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amt; j++) {
                int coin = coins[i - 1];
                if (coin > j) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }

                dp[i][j] = dp[i - 1][j] +  dp[i][j - coin];
            }
        }

        System.out.println(dp[n][amt]);
    }


    @Test
    void editDistance() {
        String s = "bag";
        String t = "pack";
        int sn = s.length();
        int tn = t.length();

        int[][] dp = new int[sn + 1][tn + 1];
        IntStream.rangeClosed(0, sn).forEach(n -> dp[n][0] = n);
        IntStream.rangeClosed(0, tn).forEach(n -> dp[0][n] = n);

        for (int i = 1; i <= sn; i++) {
            for (int j = 1; j <= tn; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                    continue;
                }

                int op = IntStream.of(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]).min().getAsInt();
                dp[i][j] = op + 1;
            }
        }

        System.out.println(11);
    }

    @Test
    void editDistanceV2() {
        String s = "bag";
        String t = "pack";
        int sn = s.length();
        int tn = t.length();

        int[] dp = new int[tn + 1];
        IntStream.rangeClosed(1, tn).forEach(j -> dp[j] = j);

        for (int i = 1; i <= sn; i++) {
            int leftup = dp[0];
            dp[0] = i;
            for (int j = 1; j <= tn; j++) {
                int temp = dp[j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] = leftup;
                    continue;
                }

                int op = IntStream.of(dp[j],  dp[j - 1], leftup).min().getAsInt();
                dp[j] = op + 1;
                leftup = temp;
            }
        }

        System.out.println(11);
    }
}
